// 从前序与中序遍历序列构造二叉树
// 方法 1 递归
var buildTree = function (preorder, inorder) {
  let n = preorder.length
  let map = {}
  for (let i = 0; i < n; i++) {
    map[inorder[i]] = i
  }
  return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1, map)
}
var myBuildTree = function (
  preorder,
  inorder,
  pleft,
  pright,
  ileft,
  iright,
  map
) {
  if (pleft > pright) return null
  let proot = pleft
  let root = new TreeNode(preorder[proot])
  let iroot = map[preorder[proot]]
  let slsubtree = iroot - ileft
  root.left = myBuildTree(
    preorder,
    inorder,
    pleft + 1,
    pleft + slsubtree,
    ileft,
    iroot - 1,
    map
  )

  root.right = myBuildTree(
    preorder,
    inorder,
    pleft + slsubtree + 1,
    pright,
    iroot + 1,
    iright,
    map
  )

  return root
}
// 方法 2 迭代
var buildTree = function (preorder, inorder) {
  if (preorder === null || preorder.length === 0) return null
  let root = new TreeNode(preorder[0])
  let stack = []
  stack.push(root)
  let iIndex = 0
  for (let i = 1; i < preorder.length; i++) {
    let preorderVal = preorder[i]
    let node = stack[stack.length - 1]
    if (node.val !== inorder[iIndex]) {
      node.left = new TreeNode(preorderVal)
      stack.push(node.left)
    } else {
      while (stack.length && stack[stack.length - 1].val === inorder[iIndex]) {
        node = stack.pop()
        iIndex++
      }
      node.right = new TreeNode(preorderVal)
      stack.push(node.right)
    }
  }
  return root
}
